import { swap } from './utils'

function partition (arr, num) {
  let pivot = -1
  let p = 0
  while (p < arr.length) {
    if (arr[p] <= num) {
      swap(arr, p, ++pivot)
    }
    p++
  }
  return pivot
}

// 荷兰国旗问题，<num, =num, >num
function partition3 (arr, num) {
  let lPivot = -1
  let rPivot = arr.length
  let p = 0
  while (p < rPivot) {
    if (arr[p] < num) {
      swap(arr, p++, ++lPivot)
    } else if (arr[p] > num) {
      swap(arr, p, --rPivot)
    } else {
      p++
    }
  }
  return [lPivot + 1, rPivot - 1] // 返回等于区域的下标
}

const arr = [9, 8, 7, 6, 5, 4, 3, 2, 1]
const pivot = partition(arr, 5)
console.log(arr)
console.log(pivot)
// 荷兰国旗问题
const arr2 = [9, 5, 8, 7, 5, 6, 5, 1, 5, 2, 3, 4]
const pivots = partition3(arr2, 5)
console.log(arr2)
console.log(pivots)
